package com.hdu.other.dp.one;

import java.util.Arrays;

public class lc91 {
    class Solution {
        public int numDecodings(String s)
        {
            int len = s.length();
            int[] dp = new int[len + 1];
            Arrays.fill(dp, -1);
            return f(
                    s,
                    0,
                    dp
            );
        }

        int f(String s, int index, int[] dp)
        {
            if (index == s.length())
            {
                return 1;
            }
            if (dp[index] != -1)
            {
                return dp[index];
            }
            if (s.charAt(index) == '0')
            {
                return 0;
            }
            int ans = f(s, index + 1, dp);
            if (index + 1 < s.length())
            {
                String curS = s.substring(index, index + 2);
                Integer num = Integer.valueOf(curS);
                if (num >= 10 && num <= 26)
                {
                    ans += f(s, index + 2, dp);
                }
            }
            return dp[index] = ans;
        }
    }
}
